//
// Description: 236. 二叉树的最近公共祖先
// Created by Loading on 2021/12/11.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    // 空树，或已找到其中一个节点，直接返回
    if (!root || root->val == p->val || root->val == q->val) {
        return root;
    }
    // 在左右子树中寻找
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    // 其中一个为空，则在另一个里找
    if (!left) {
        return right;
    }
    if (!right) {
        return left;
    }
    // 都不为空，则当前节点即为最近公共祖先
    return root;
}

int main() {
    vector<int> nums = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
    auto root = generateTreeNode(nums);
    auto p = new TreeNode(5);
    auto q = new TreeNode(1);
    auto res = lowestCommonAncestor(root, p, q);
    cout << res->val << endl;

    return 0;
}